class Sorter {

    static quickSort(arr, compare = (a, b) => a < b) {

        function swap(i, j) {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        
        function partition(start, end) {
            let low = start, 
                high = end + 1, 
                sentinel = arr[start];
            while(true) {
                // 1. 让低位指针向上移动
                while(compare(arr[++low], sentinel) && low < end);
                // 2. 让高位指针向下移动
                while(compare(sentinel, arr[--high]) && high > start);
                // 3. 这里注意，一定要判定一下，防止跑偏
                if(low >= high) break;
                // 4. 交换高低位
                swap(low, high);
            }
            // 5. 这里要用high和start交换
            swap(high, start);
            return high;
        }

        function sort(start, end) {
            if(start >= end) return;
            let splitIndex = partition(start, end);
            sort(start, splitIndex - 1);
            sort(splitIndex + 1, end);
        }

        sort(0, arr.length - 1);
        return arr;
    }
}

exports.Sorter = Sorter;
